package treeTraversal;

import offer.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.Stack;

/**
 * @Auther: wangliuyang
 * @Date: 2021/4/25 16:10
 * @Description: 二叉树前序遍历得三种方式
 */
public class PreorderTraversal {
    public static void preorderTraversal1(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        preorderTraversal1(root.left);
        preorderTraversal1(root.right);
    }

    public static void preorderTraversal2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        stack.push(cur);
        while (!stack.isEmpty()) {
            cur = stack.pop();
            System.out.println(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    /**
     * Desc: Morris,有左节点得节点会来到两次，其他都来一次
     * 先序遍历只需要在第二次来到时访问即可
     *
     * @param root
     * @return
     * @author wangliuyang
     * @date
     */
    public static void preOrderTraversal3(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (cur.left != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    //第一次访问节点
                    System.out.println(cur.val + "");
                    mostRight.right = cur;//记录头节点，同时记录了过已经访问
                    cur = cur.left;
                    continue;
                } else if (mostRight.right == cur) {
                    //第二次访问节点
                    //System.out.println(cur.val + "");
                    mostRight.right = null;
                }
            }else {
                System.out.println(cur.val);
            }
            cur = cur.right;
        }
    }
}

